package com.zwj.interview.动态规划;

/**
 * 题目：
 * 给定一个非空的正整数数组和一个目标值S，如果为每个数字添加“+”或“-”运算符，
 * 请计算有多少种方法可以使这些整数的计算结果为S。例如，如果输入数组[2，2，2]并且S等于2，
 * 有3种添加“+”或“-”的方法使结果为2，它们分别是2+2-2=2、2-2+2=2及-2+2+2=2
 */
public class 添加操作符的目标和_背包问题 {


    /**
     * 分析：
     * 为输入的数组中的有些数字添加“+”，有些数字添加“-”。如果所有添加“+”的数字之和为p，
     * 所有添加“-”的数字之和为q，按照题目的要求，p-q=S。如果累加数字中的所有数字，
     * 就能得到整个数组的数字之和，记为sum，即p+q=sum。将这两个等式的左右两边分别相加，
     * 就可以得到2p=S+sum，即p=（S+sum）/2
     * 那么问题最终就转为：
     * nums中存在几个子集A，使得A中所有元素的和为（S+sum）/2，我们说子集划分问题就属于背包问题
     * <p>
     * 有一个背包，容量为sum，现在有N个物品，第i个物品的重量为nums[i-1]，每个物品只有一个，请问有几种方法能够
     * 恰好装满这个容器
     * <p>
     * 我们定义dp[i][j]=x 表示，若只在前i个物品中选择，且当前背包的容量为j，则最多有x种方法可以恰好装满背包
     * 等价于
     * 若只在nums的前i个元素中选择，目标和为j，则最多有x种方法划分子集
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //这两种情况，不可能存在合法的划分方法，第一种是sum+target不是2的倍数，这样的话，(sum + target) / 2就除不尽了
        if ((sum + target) % 2 == 1 || sum < target) {
            return 0;
        }
        return subsetSum(nums, (sum + target) / 2);
    }

    /**
     * 计算nums中有几个子集和为target
     *
     * @param nums
     * @param target
     * @return
     */
    private int subsetSum(int[] nums, int target) {
        int n = nums.length;
        int[][] dp = new int[n + 1][target + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                if (j >= nums[i - 1]) {
                    //dp[i-1][j]表示不将第i个物品放入背包，则结果就跟之前的一样
                    //dp[i-1][j-nums[i-1]]表示将第i个物品放入背包
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                } else {
                    //放不下不能再放了
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][target];
    }
}
